Algorithmic Thinking for Adventurous Minds: Quest for Fundamental Algorithms with Visualization and Python by Xu Claire & Xu Raymond & Xu William

Author:Xu, Claire & Xu, Raymond & Xu, William [Xu, Claire]
Language: eng
Format: epub
Published: 2021-04-26T00:00:00+00:00

Table 2.10

Coin Change Problem: coupon values and total amount to change

“We’re in the academy.” the store owner says, “as our customer, you shall prove your intelligence by using the least number of coupons for your purchase.”

At the speed of light, Banana Split sorts through the coupons and picks the higher face values by order: one $6 and four $1 coupons.

“Wait! Let’s double check… well… two $5 coupons are clearly better.” Dark Knight states, as he does his due diligence.

“But how come our greedy approach worked just fine when selling the CalliLens in Greedy-ent Mart?!?” Bubble Gum asks, surprised.

Pause here. Can you spot the difference between the two problems?

“Hmm...let’s carefully examine the two sets of face values,” Banana Split reminds the group, “the US bill system has $1, $5, $10, $20, $50, and $100. Whereas the store coupons have $1, $5, and $6.”

Which set of numbers works for Greedy and which doesn’t?

Answer:

In cases where there is a bill whose value ($6) is added to the smallest bill ($1), is lower than twice that of the bill immediately less than it ($5), the Greedy approach will not work. In this case, $6 + $1 < 2 x $5. That’s why!

“Wow, that’s eye-opening!” Banana Split exclaims intrigued, “this is an optimization problem. If we cannot go with Greedy, let’s try it with DP! Does this problem have the two DP properties?”

They peer through CalliLens together.

If we have an unlimited number for each bill type S[]=[S1, S2, Sm], what’s the solution to select the least number of bills to pay price N. Use a function to represent the solution: f(N).

In our case, S[]=[$1, $5, $6], N = 10

Optimal Substructure

Let Sj be the last bill added to the optimal solution. So the total number of bills is 1 (last bill) + the number of bills to make up

N-Sj: f(N) = 1 + f(N-Sj)

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.